package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC523 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 只能说，妙啊！
     * 翻译成人话：
        假设位置 j < i :
        0 到 j 的前缀和 preSum1 = 某常数1 * k + 余数1
        0 到 i 的前缀和 preSum2 = 某常数2 * k + 余数2
        当找到 余数1 等于 余数2时， 则 j + 1 到 i 的连续和 = preSum2 - preSum1 = (某常数2 - 某常数1) * k， 必为 k 的倍数， 返回true
     * @return:
     */
    public class Solution {

        public boolean checkSubarraySum(int[] nums, int k) {
            int sum = 0;

            // key：区间 [0..i] 里所有元素的和 % k
            // value：下标 i
            Map<Integer, Integer> map = new HashMap<>();
            // 理解初始化的意义
            map.put(0, -1);
            int len = nums.length;
            for (int i = 0; i < len; i++) {
                sum += nums[i];
                if (k != 0) {
                    sum = sum % k;
                }

                if (map.containsKey(sum)) {
                    if (i - map.get(sum) > 1) {
                        return true;
                    }
                } else {
                    map.put(sum, i);
                }

            }
            return false;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC523 an = new LC523();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
